class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int lenY = dungeon.length, lenX = dungeon[0].length;
        int[][] dp = new int[lenY + 1][lenX + 1];
        for (int i = 0; i <= lenY; ++i) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[lenY][lenX - 1] = dp[lenY - 1][lenX] = 1;
        for (int i = lenY - 1; i >= 0; i--) {
            for (int j = lenX - 1; j >= 0; j--) {
                int minNext = Math.min(dp[i + 1][j], dp[i][j + 1]);
                dp[i][j] = Math.max(minNext - dungeon[i][j], 1);
            }
        }
        return dp[0][0];
    }
}